/**
    ******************************************************************************
    * @file    rbTree.c
    * @author  debian
    * @version V1.0.0
    * @date    2019-12-31
    * @brief   红黑树
    ******************************************************************************
    * @attention
    *
    *
    ******************************************************************************
    */ 

/* Includes ------------------------------------------------------------------*/
#include "rbTree.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

/** @addtogroup DataStruct_Driver
    * @{
    */

/** @addtogroup rbTree
    * @{
    */

/* Private typedef -----------------------------------------------------------*/

/* Private define ------------------------------------------------------------*/

/* Private macro -------------------------------------------------------------*/

/* Private variables ---------------------------------------------------------*/

/* Private function prototypes -----------------------------------------------*/

/* Private functions ---------------------------------------------------------*/


/** @defgroup rbTree_Exported_Functions rbTree Exported Functions
    * @{
    */

/** @defgroup rbTree_Exported_Functions_Group1 Initialization and deinitialization functions
    *  @brief    Initialization and Configuration functions
    *
@verbatim    
    ===============================================================================
                ##### Initialization and deinitialization functions #####
    ===============================================================================
    [..]
        This section provides functions allowing to initialize and de-initialize the rbTree
        to be ready for use.
 
@endverbatim
    * @{
    */ 

    
/**
    * @}
    */

/** @defgroup rbTree_Exported_Functions_Group2 operation functions 
    *  @brief   operation functions
    *
@verbatim   
    ===============================================================================
                        ##### operation functions #####
    ===============================================================================
    [..]
        This subsection provides a set of functions allowing to manage the rbTree.

@endverbatim
    * @{
    */

        /**
		    * @brief  左旋
		    * @param  
		    * @retval 
		    */ 
		    static int rbTree_left_Rotate(struct rbTree *T, struct rbTree_node *x)
		    {
				//获取x的右孩子y
				struct rbTree_node *y = x->rbst.right;

				//1.调整x父结点的孩子指向y,y的parent指针执行x的父
				y->rbst.parent = x->rbst.parent;
				if(x->rbst.parent == T->nil) {					//注意这个nil结点
					T->root = y;
				} else if(x == x->rbst.parent.left)  {
					x->rbst.parent.left = y;
				} else if(x == x->rbst.parent.right)  {
					x->rbst.parent.right = y;
				} 

				//2.y左孩子挂在x右孩子上
				x->rbst.right = y->rbst.left;
				if(y->rbst.left != T->nil)  {
					y->rbst.left->bst.parent = x;
				}
				
				//3.x成为y的左孩子
				y->rbst.left = x;
				x->rbst.parent = y;
			
		        return 0;
		    }


		/**
		    * @brief  右旋
		    * @param  
		    * @retval 
		    */ 
		    static int rbTree_right_Rotate(struct rbTree *T, struct rbTree_node *y)
		    {
				//获取y的左孩子x
				struct rbTree_node *x = y->rbst.left;

				//1.调整y父结点的孩子指向x,x的parent指针执行x的父
				x->rbst.parent = y->rbst.parent;
				if(y->rbst.parent == T->nil) {					//注意这个nil结点
					T->root = x;
				} else if(y == y->rbst.parent.left)  {
					y->rbst.parent.left = x;
				} else if(y == y->rbst.parent.right)  {
					y->rbst.parent.right = x;
				} 

				//2.x右孩子挂在y左孩子上
				y->rbst.left = x->rbst.right;
				if(x->rbst.right != T->nil)  {
					x->rbst.right->bst.parent = y;
				}
				
				//3.y成为x的右孩子
				x->rbst.right = y;
				y->rbst.parent = x;
			
		        return 0;
		    }


		/**
		    * @brief  红黑树插入调整
		    * @param  
		    * @retval 
		    */ 
		    static int rbTree_insert_fixup(struct rbTree *T, struct rbTree_node *z)
			{
				//父结点是nil结点，比较父结点是红色的，需要调整
				while(z->rbst.parent->rbst.color == RED)
				{
					//叔父结点是在右子树上
					if(z == z->rbst.parent->rbst.parent->rbst.left) {
						//判断叔父结点的颜色
						struct rbTree_node *y = z->rbst.parent->rbst.parent->rbst.right;
						if(y->rbst.color == RED) {
							//父结点和叔父结点同时变成黑色，祖父结点变成红色，z的指针往上移动两层，继续遍历
							z->rbst.parent->rbst.color = BLACK;
							y->rbst.color = BLACK;
							z->rbst.parent->rbst.parent->rbst.color = RED;
							z = z->rbst.parent->rbst.parent;
						} else {
							if(z == z->rbst.parent->rbst.right) {		//叔父结点是黑色并且z是右孩子
								z = z->rbst.parent;
								rbTree_left_Rotate(T, z);
							}

							z->rbst.parent->rbst.color = BLACK;			//叔父结点为黑色并且z是左孩子
							z->rbst.parent->rbst.parent->rbst.color = RED;
							rbTree_right_Rotate(T, z->rbst.parent->rbst.parent);
						}
					}else {
						//判断叔父结点的颜色
						struct rbTree_node *y = z->rbst.parent->rbst.parent->rbst.left;
						if(y->rbst.color == RED) {
							//父结点和叔父结点同时变成黑色，祖父结点变成红色，z的指针往上移动两层，继续遍历
							z->rbst.parent->rbst.color = BLACK;
							y->rbst.color = BLACK;
							z->rbst.parent->rbst.parent->rbst.color = RED;
							z = z->rbst.parent->rbst.parent;
						} else {
							if(z == z->rbst.parent->rbst.left) {		//叔父结点是黑色并且z是左孩子
								z = z->rbst.parent;
								rbTree_right_Rotate(T, z);				//左旋后，变成是右孩子了
							}

							z->rbst.parent->rbst.color = BLACK;			//叔父结点为黑色并且z是右孩子
							z->rbst.parent->rbst.parent->rbst.color = RED;
							rbTree_left_Rotate(T, z->rbst.parent->rbst.parent);
						}
					}
				}

				T->root->rbst.color = BLACK;
				return 0;
			}


		/**
		    * @brief  创建结点
		    * @param  
		    * @retval 
		    */ 
		    static struct rbTree_node* rbTree_creat_node(struct rbTree *T, Elemtype data, _color color)
			{
				//申请一个结点
				struct rbTree_node *node = (struct rbTree_node *)malloc(sizeof(struct rbTree_node));
				assert(node);

				//填充数据
				node->data = data;
				node->bst.color = color;
				node->bst.left = T->nil;
				node->bst.right = T->nil;
				node->bst.parent = T->nil;

				return node;
			}	


		/**
			* @brief  红黑树插入操作
			* @param  
			* @retval 
			*/ 
			static int rbTree_Insert(struct rbTree *T, struct rbTree_node *z)
			{
				struct rbTree_node *y = T->nil;					//y是x的父节点
				struct rbTree_node *x = T->root;				//x是查找当前要插入的结点
				//循环遍历找到要插入的位置
				while(x != T->nil)
				{
					y = x;
					if(z->data < x->data)  {	//数据小于data,往左子树
						x = x->rbst.left;
					} else if(z->data > x->data) {
						x = x->rbst.right;
					}else {   					//两个数相等退出
						return -1;
					}
				}

				//把z挂接到y的孩子上
				z->rbst.parent = y;				//把z的父结点指针指向y
				if(z->rbst.parent == T->nil)  {   	//如果z的父节点为nil，说明现在是空树
					T->root = z;
				} else if(z->data < y->data ) { 	//数据比根结点数据小，挂在左子树上
					y->rbst.left = z;
				} else {
					y->rbst.right = z;
				}
				
				//调整
				rbTree_insert_fixup(T, z);
				return 0;
			}

		/**
			* @brief  查找x为根结点的子树的最小结点
			* @param  
			* @retval 
			*/ 
			static struct rbTree_node *rbTree_Min(struct rbTree *T, struct rbTree_node *x)
			{
				while(x->bst.left != T->nil)
				{
					x = x->bst.left;
				}

				return x;
			}

		/**
			* @brief  查找x为根结点的子树的最大结点
			* @param  
			* @retval 
			*/ 
			static struct rbTree_node *rbTree_Max(struct rbTree *T, struct rbTree_node *x)
			{
				while(x->bst.right != T->nil)
				{
					x = x->bst.right;
				}

				return x;
			}
		
			/**
				* @brief  查找x为根结点的子树的最大结点
				* @param  
				* @retval 
				*/ 
				static struct rbTree_node *rbTree_search(struct rbTree *T,       Elemtype data)
				{
					struct rbTree_node *node = T->root;

					while(node != T->nil)
					{
						if(data < node->data) {
							node = node->rbst.left;
						} else if(data > node->data) {
							node = node->rbst.right;
						}else  {
							return node;
						}
					}
	
					return T->nil;
				}

		/**
			* @brief  查找x为根结点的子树的最大结点
			* @param  
			* @retval 
			*/ 
			static struct rbTree_node *rbTree_successor(struct rbTree *T, rbTree_node *x)
			{
				struct rbTree_node *y = x->rbst.parent;	
		
				//如果有右子树的话，就直接找右子树的最小值，就是直接后继
				if(x->rbst.right != T->nil) {
					return rbTree_Min(T, x->rbst.right);
				}

				//如果没有右子树，就往父结点走，当遇到一个为左子树的时候，这个时候的父结点就是直接后继
				while((y != T->nil) && (x == y->rbst.right))  {   //后面的判断条件如果是left的话，就说明找到了直接后继
					x = y;
					y = y->rbst.parent;
				}

				return y;
			}

		/**
		    * @brief  红黑树插入调整
		    * @param  
		    * @retval 
		    */ 
		    static int rbTree_delete_fixup(struct rbTree *T, struct rbTree_node *x)
			{
				while(x != T->root && x->rbst.color == BLACK)
				{
					if(x == x->rbst.left)    {					//x是左孩子	
						struct rbTree_node *w = x->rbst.parent->rbst.right;

						if(w->rbst.color == RED)		{			//情况1：x的兄弟结点w是红色的
							w->rbst.color = BLACK;
							x->rbst.parent->rbst.color = RED;
							rbTree_left_Rotate(T, x->rbst.parent);
							w = x->rbst.parent->rbst->right;
						}  

						if(w->rbst.left->rbst.color == BLACK && w->rbst.right->rbst.color == BLACK) {   
							//情况2：x的兄弟结点w是黑色的，而且w的两个子结点都是黑色的。

							w->rbst.color = RED;		//因为x少了一个黑色结点，所以要把w的这边也少一个黑色
							x = x->rbst.parent;			//再把x的指针往上移动，但是现在这个x还是确实一个黑色，还要继续调整
						} else  {
							if(w->rbst.right->rbst.color == BLACK)  {		//情况3：x的兄弟结点是w黑色结点，w的右孩子是黑色的
								w->rbst.left->rbst.color = BLACK;
								w->rbst.color = RED;
								rbTree_right_Rotate(T, w);
								w = x->rbst.parent->rbst.right;
							} 

							//情况4：x的兄弟结点是w黑色结点，且w的右孩子是红色的
							w->rbst.color = x->rbst.parent->rbst.color;    //x的父节点的颜色赋值给w结点的颜色
							w->rbst.parent->rbst.color = BLACK;			   //x的父节点的颜色赋值成黑色
							w->rbst.right->rbst.color = BLACK;			   //w的右孩子的颜色赋值成黑色
							rbTree_left_Rotate(T, x->rbst.parent);		   //然后以x的父节点为轴心右旋

							x = T->root;
						}

					} else if(x == x->rbst.right)	{			//x是右孩子
						struct rbTree_node *w = x->rbst.parent->rbst.left;

						if(w->rbst.color == RED)		{			//情况1：x的兄弟结点w是红色的
							w->rbst.color = BLACK;
							x->rbst.parent->rbst.color = RED;
							rbTree_right_Rotate(T, x->rbst.parent);
							w = x->rbst.parent->rbst->left;
						}  
						
						if(w->rbst.left->rbst.color == BLACK && w->rbst.right->rbst.color == BLACK) {   
							//情况2：x的兄弟结点w是黑色的，而且w的两个子结点都是黑色的。

							w->rbst.color = RED;		//因为x少了一个黑色结点，所以要把w的这边也少一个黑色
							x = x->rbst.parent;			//再把x的指针往上移动，但是现在这个x还是确实一个黑色，还要继续调整
						} else  {
							if(w->rbst.left->rbst.color == BLACK)  {		//情况3：x的兄弟结点是w黑色结点，w的左孩子是黑色的
								w->rbst.right->rbst.color = BLACK;
								w->rbst.color = RED;
								rbTree_left_Rotate(T, w);
								w = x->rbst.parent->rbst.left;
							} 

							//情况4：x的兄弟结点是w黑色结点，且w的左孩子是红色的
							w->rbst.color = x->rbst.parent->rbst.color;    //x的父节点的颜色赋值给w结点的颜色
							x->rbst.parent->rbst.color = BLACK;			   //x的父节点的颜色赋值成黑色
							w->rbst.left->rbst.color = BLACK;			   //w的左孩子的颜色赋值成黑色
							rbTree_right_Rotate(T, x->rbst.parent);		   //然后以x的父节点为轴心右旋

							x = T->root;
						}
					}				
				}

				x->rbst.color = BLACK;
				return 0;
		    }

		/**
			* @brief  红黑树插入操作
			* @param  x结点替换y结点
			* @retval 
			*/ 
			static int rbTree_replace(struct rbTree *T, struct rbTree_node *y, struct rbTree_node *x)
			{
				if(y->rbst.parent == T->nil)  { 				//y是根结点
					T->root = x;	
				} else if(y == y->rbst.parent->rbst.left)  { 	//x是y的左孩子
					y->rbst.parent->rbst.left = x;
				} else if(y == y->rbst.parent->rbst.right)  {	//x是y的右孩子
					y->rbst.parent->rbst.right = x;
				}
				x->rbst.parent = y->rbst.parent;

				return 0;
			}


		/**
			* @brief  红黑树删除操作
			* @param  
			* @retval 
			*/ 
			int rbTree_Delete(struct rbTree *T, struct rbTree_node *z)
			{
				struct rbTree_node *y = z;					//y是指向要被删除的结点或者是移动的结点
				struct rbTree_node *x = T->nil;	

				_color y_old_color = y->rbst.color;			//保存y以前的颜色

				if(z->rbst.left == T->nil)  {				//删除的z没有左孩子
					x = z->rbst.right;						//保存x结点，x结点也是有移动过的
					rbTree_replace(T, z, z->rbst.right);	//用x替换到y
				} else if(z->rbst.right == T->nil)  {
					x = z->rbst.left;						//保存x结点，x结点也是有移动过的
					rbTree_replace(T, z, z->rbst.left);		//用x替换到y
				} else {
					y = rbTree_successor(T, z);				//查找直接后继
					y_old_color = y->rbst.color;
					
					x = y->rbst.right;

					if(z == y->rbst.parent)   {				//如果y就是z的孩子
						x->rbst.parent = y;
					}  else  {
						rbTree_replace(T, y, y->rbst.right);	//先把y结点给替换掉
						y->rbst.right = z->rbst.right;			//把z的右子树挂在到y的右子树上
						y->rbst.right->rbst.parent = y;
					}
	
					rbTree_replace(T, z, y);		//用x替换到y
					//y结点替换z结点
					y->rbst.left = z->rbst.left;
					y->rbst.left->rbst.parent = y;
					y->rbst.color = z->rbst.color;
				}
				
				//调整
				free(z);
				if(y_old_color == BLACK)
					rbTree_delete_fixup(T, x);
				return 0;
			}

		

		#if 1
		/**
			* @brief  前序遍历,先遍历根结点，再左子树，然后右子树
			* @param	
			* @retval 
			*/ 
			static  void bstree_preOrderTraversal(struct rbTree_node* node)
			{	
				if(node == NULL)
					return ;

				printf("%d %d ", node->data, node->bst.color);
				bstree_preOrderTraversal(node->bst.left);
				bstree_preOrderTraversal(node->bst.right);	
			}


		int main()
		{
			int i = 0;
			int ret = -1;
			int keyArray[20] = {24,25,13,35,23, 26,67,47,38,98, 20,19,17,49,12, 21,9,18,14,15};
	
			struct rbTree T = {0};		//红黑树头结点

			//创建nil结点
			T->nil = rbTree_creat_node(&T, 0, BLACK);

			//开始根结点指向nil
			T->root = T->nil;

			//申请变量
			struct rbTree_node *node = T->nil;
			
			//循环插入
			for(i=0; i<sizeof(keyArray)/sizeof(keyArray[0]); i++)
			{
				node = rbTree_creat_node(&T, keyArray[i], RED); 
				rbTree_Insert(&T, node)
				bstree_preOrderTraversal(T.root);
				printf("\n");
			}
			
			
			return 0;
	
		}
	#endif

    /**
    * @}
    */


/**
    * @}
    */

/**
    * @}
    */

/**
    * @}
    */

/************************ (C) 2019 HOME 深圳龙华 *****END OF FILE****/

